# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.mid_list, res = [], 0
        if root:
            self.search(root, "")
        for s in self.mid_list:
            res += int(s)
        return res

    def search(self, root: TreeNode, s: str):
        mid_s = s + str(root.val)
        if not root.left and not root.right:
            self.mid_list.append(mid_s)
        else:
            if root.left:
                self.search(root.left, mid_s)
            if root.right:
                self.search(root.right, mid_s)


class Solution2:
    def sumNumbers(self, root: TreeNode) -> int:
        self.mid_list, res = [], 0
        if root:
            self.search(root, 0)
        for s in self.mid_list:
            res += s
        return res

    def search(self, root: TreeNode, s: int):
        mid_s = s * 10 + root.val
        if not root.left and not root.right:
            self.mid_list.append(mid_s)
        else:
            if root.left:
                self.search(root.left, mid_s)
            if root.right:
                self.search(root.right, mid_s)


a = Solution2()
b = TreeNode(1)
b.left = TreeNode(2)
b.right = TreeNode(3)
print(a.sumNumbers(b))
